package demo18;

import demo17.Tree45;

import java.util.Stack;

public class Tree46 {
    static class TreeNode47{
        public char val;
        public TreeNode47 left;
        public TreeNode47 right;

        public TreeNode47(char val) {
            this.val = val;
        }
    }
    public TreeNode47 create5() {
        TreeNode47 head = new TreeNode47('A');
        TreeNode47 head2 = new TreeNode47('B');
        TreeNode47 head3 = new TreeNode47('C');
        TreeNode47 head4 = new TreeNode47('D');
        TreeNode47 head5 = new TreeNode47('E');
        TreeNode47 head6 = new TreeNode47('F');
        head.left = head2;
        head.right = head3;
        head2.left = head4;
        head2.right = head5;
        head3.left = head6;
        return head;
    }
    //二叉树的非递归后遍历实现
    public void postOrder(TreeNode47 head){
        if(head==null){
            return;
        }
        TreeNode47 cur=head;
        TreeNode47 pre=null;
        Stack<TreeNode47> s=new Stack<>();
        while (cur!=null||!s.isEmpty()){
            while(cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            TreeNode47 top=s.peek();
            if(top.right==null||top.right==pre){
                System.out.print(top.val+" ");
                s.pop();
                pre=top;
            }else{
                cur=top.right;
            }
        }
    }
}
